import org.junit.Test;

import java.util.List;

public class LinkList {


    /**
     *
     * @Description：无头单向非循环链表实现
     */
    public class MySingleList {

        /**
         * 节点内部类
         */
        class ListNode {
            public int val;
            public ListNode next;

            public ListNode(int val) {
                this.val = val;
            }
        }

        public ListNode head;//不初始化了 默认就是null


        public void createList() {
            ListNode listNode1 = new ListNode(12);
            ListNode listNode2 = new ListNode(23);
            ListNode listNode3 = new ListNode(34);
            ListNode listNode4 = new ListNode(45);
            ListNode listNode5 = new ListNode(56);
            listNode1.next = listNode2;
            listNode2.next = listNode3;
            listNode3.next = listNode4;
            listNode4.next = listNode5;
            this.head = listNode1;
        }

        /**
         * 打印链表里面的数据
         */
        public void display() {
            ListNode cur = this.head;
            while (cur != null) {
                System.out.print(cur.val + " ");
                cur = cur.next;
            }
        }

        //得到单链表的长度
        public int size() {
            int length = 0;
            if (this.head == null) {
                return length;
            }
            ListNode p = this.head;
            while (p != null) {
                length++;
                p = p.next;
            }
            return length;
        }

        //头插法
        public void addFirst(int data) {
            ListNode newNode = new ListNode(data);
            //头插
            newNode.next = this.head;
            //更新head指针
            head = newNode;
        }

        //尾插法
        public void addLast(int data) {
            int length = this.size();
            ListNode p = this.head;
            //走到链尾 length-1步
            while (length > 1) {
                p = p.next;
                length--;
            }
            //尾部插入
            p.next = new ListNode(data);
        }

        //任意位置插入,第一个数据节点为0号下标
        public void addIndex(int index, int data) {
            if (index < 0 || index > this.size() - 1) {
                throw new IndexWrongfulException("index不合法");
            }
            if(index == 0){
                this.addFirst(data);
                return;
            }
            if(index == this.size() - 1){
                this.addLast(data);
                return;
            }
            ListNode p = this.head;
            while (index - 1 > 0) {
                p = p.next;
                index--;
            }
            ListNode newNode = new ListNode(data);
            newNode.next = p.next;
            p.next = newNode;
            return;
        }

        //查找是否包含关键字key是否在单链表当中
        public boolean contains(int key) {
            return false;
        }

        //删除第一次出现关键字为key的节点
        public void remove(int key) {

        }

        //删除所有值为key的节点
        public void removeAllKey(int key) {
            if (head == null){
                return;
            }
            ListNode p = this.head.next,pPre = this.head;
            while(p != null){
                if(p.val == key){
                    pPre.next= p.next;
                }else{
                    pPre= p;
                }
                p = p.next;
            }
            if(head.val == key){
                head = head.next;
            }
        }


        public void clear() {
            this.head = null;
        }


    }

    public MySingleList getMySingleList() {
        MySingleList mySingleList = new MySingleList();
        return mySingleList;
    }
}
